
/**
 * 
 * 单链表的排序
 * 
 * 描述

给定一个节点数为n的无序单链表，对其按升序排序。

数据范围：
0
<
n
≤
100000
0<n≤100000，保证节点权值在
[
−
1
0
9
,
1
0
9
]
[−10 
9
 ,10 
9
 ]之内。
要求：空间复杂度 
O
(
n
)
O(n)，时间复杂度 
O
(
n
l
o
g
n
)
O(nlogn)
 */
public class 单链表的排序 {
    
    public static void main(String[] args) {
        
        ListNode node = new ListNode(1);
        node.next = new ListNode(3);
        node.next.next = new ListNode(2);
        node.next.next.next = new ListNode(4);
        node.next.next.next.next = new ListNode(5);

        ListNode result = sortInList(node);

        System.err.println(result.toString());

    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public static ListNode sortInList (ListNode head) {
        // write code here
        if (head == null || head.next == null) {
            return head;
        }
        // 找到链表中间节点
        ListNode mid = getMiddle(head);
        ListNode midNext = mid.next;
        mid.next = null;
        // 递归排序两个子链表
        ListNode left = sortInList(head);
        ListNode right = sortInList(midNext);
        // 合并两个已排序的子链表
        return mergeTwoLists(left, right);
    }

    private static ListNode getMiddle(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast!= null && fast.next!= null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while (l1!= null && l2!= null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        if (l1!= null) {
            curr.next = l1;
        }
        if (l2!= null) {
            curr.next = l2;
        }
        return dummy.next;
    }
}
